const arr = [1, 5, 2, 1, 4, 9, 6]

function mergeSort(arr) {
  let len = arr.length
  if (len <= 1) {
    return arr
  }
  let mid = Math.floor(len / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))

  let res = merge(left, right)

  return res
}

function merge(arr1, arr2) {
  let len1 = arr1.length, len2 = arr2.length
  let i = 0, j = 0
  let res = []
  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i])
      i++
    } else {
      res.push(arr2[j])
      j++
    }
  }

  if (i < len1) {
    res = res.concat(arr1.slice(i))
  } else {
    res = res.concat(arr2.slice(j))
  }

  return res
}

console.log(mergeSort(arr));
